{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Time Needed to Buy Tickets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: timeRequiredToBuy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #买票需要的时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个人前来排队买票，其中第 <code>0</code> 人站在队伍 <strong>最前方</strong> ，第 <code>(n - 1)</code> 人站在队伍 <strong>最后方</strong> 。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>tickets</code> ，数组长度为 <code>n</code> ，其中第 <code>i</code> 人想要购买的票数为 <code>tickets[i]</code> 。</p>\n",
    "\n",
    "<p>每个人买票都需要用掉 <strong>恰好 1 秒</strong> 。一个人 <strong>一次只能买一张票</strong> ，如果需要购买更多票，他必须走到&nbsp; <strong>队尾</strong> 重新排队（<strong>瞬间 </strong>发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 <strong>离开</strong> 队伍。</p>\n",
    "\n",
    "<p>返回位于位置 <code>k</code>（下标从 <strong>0</strong> 开始）的人完成买票需要的时间（以秒为单位）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>tickets = [2,3,2], k = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong> \n",
    "- 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。\n",
    "- 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。\n",
    "位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>tickets = [5,1,1,1], k = 0\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>\n",
    "- 第一轮，队伍中的每个人都买到一张票，队伍变为 [4, 0, 0, 0] 。\n",
    "- 接下来的 4 轮，只有位置 0 的人在买票。\n",
    "位置 0 的人成功买到 5 张票，用掉 4 + 1 + 1 + 1 + 1 = 8 秒。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == tickets.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= tickets[i] &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= k &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [time-needed-to-buy-tickets](https://leetcode.cn/problems/time-needed-to-buy-tickets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [time-needed-to-buy-tickets](https://leetcode.cn/problems/time-needed-to-buy-tickets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,2]\\n2', '[5,1,1,1]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        num_sum = 0\n",
    "        for index,i in enumerate(tickets):\n",
    "            if index<=k:\n",
    "                if i>=tickets[k]:\n",
    "                    num_sum = num_sum + tickets[k]\n",
    "                else: num_sum = num_sum + i\n",
    "            else:\n",
    "                if i>=tickets[k]:\n",
    "                    num_sum = num_sum + tickets[k] - 1\n",
    "                else: num_sum = num_sum + i\n",
    "        return num_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        s = sum([n >= tickets[k] for n in tickets[k + 1:]])\n",
    "        while True:\n",
    "            if tickets[k] == 0:\n",
    "                return ans - s\n",
    "            m = float(\"INF\")\n",
    "            for n in tickets:\n",
    "                if 0 < n < m:\n",
    "                    m = n\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] -= m\n",
    "                    ans += m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        s = sum([n >= tickets[k] for n in tickets[k + 1:]])\n",
    "        while True:\n",
    "            if tickets[k] == 0:\n",
    "                return ans - s\n",
    "            m = float(\"INF\")\n",
    "            for n in tickets:\n",
    "                if 0 < n < m:\n",
    "                    m = n\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] -= m\n",
    "                    ans += m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        # res = 0\n",
    "        # for i in range(len(tickets)):\n",
    "        #     if i <= k:\n",
    "        #         res += min(tickets[i], tickets[k])\n",
    "        #     else:\n",
    "        #         res += min(tickets[i], tickets[k] - 1)\n",
    "        \n",
    "        # return res\n",
    "        top = 0\n",
    "        while tickets[k] > 0:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] > 0:\n",
    "                    top+=1\n",
    "                tickets[i] -= 1\n",
    "                if tickets[k] == 0:\n",
    "                    return top\n",
    "        return top"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        time=0\n",
    "        n=len(tickets)\n",
    "        while tickets[k]!=0:\n",
    "            for i in range(n):\n",
    "                if tickets[i]!=0:\n",
    "                    time+=1\n",
    "                    tickets[i]-=1\n",
    "                if tickets[k]==0:\n",
    "                    return time\n",
    "               \n",
    "\n",
    "            \n",
    "       \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(tickets)\n",
    "        i = 0\n",
    "        while tickets[k]:\n",
    "            if tickets[i]:\n",
    "                tickets[i] -= 1\n",
    "                res += 1\n",
    "            i += 1\n",
    "            if i == n:\n",
    "                i = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        result = 0\n",
    "\n",
    "        while tickets[k] != 0:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] -= 1\n",
    "                    result += 1\n",
    "                if tickets[k] == 0:\n",
    "                    return result\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def timeRequiredToBuy(self, tickets, k):\n",
    "        return sum(min(tickets[k], x) for x in tickets[ : k + 1]) + sum(min(tickets[k] - 1, x) for x in tickets[k + 1 :])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        queue = collections.deque(range(n))\n",
    "        time = 0\n",
    "        while queue:\n",
    "            time += 1\n",
    "            cur = queue.popleft()\n",
    "            if tickets[cur] -1 >0  :\n",
    "                tickets[cur] -= 1\n",
    "                queue.append(cur)\n",
    "            else:\n",
    "                tickets[cur] -= 1\n",
    "            if tickets[k] == 0:\n",
    "                return time\n",
    "        return time\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        for i in range(tickets[k]-1):\n",
    "            for j in range(len(tickets)):\n",
    "                if tickets[j]!=0:\n",
    "                    tickets[j]=tickets[j]-1\n",
    "                    res+=1\n",
    "        for i in range(k+1):\n",
    "            if tickets[i]>0:\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        L, K, T = len(tickets), tickets[k], tickets[k]\n",
    "        for i in range(L):\n",
    "            if i < k:\n",
    "                T += min(tickets[i], K)\n",
    "            elif i > k:\n",
    "                T += min(tickets[i], K-1)\n",
    "        return T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        cnt = tickets[k]\n",
    "        time = 0\n",
    "        n = len(tickets)\n",
    "        while cnt:\n",
    "            while k >= 0:\n",
    "                current = tickets.pop(0)\n",
    "                current -= 1\n",
    "                time += 1\n",
    "                if current:\n",
    "                    tickets.append(current)\n",
    "                else:\n",
    "                    n -= 1\n",
    "                k -= 1\n",
    "            k = n - 1\n",
    "            cnt -= 1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        q = deque([[x, i] for i, x in enumerate(tickets)])\n",
    "        ans = 0\n",
    "        while q:\n",
    "            ans += 1\n",
    "            t, i = q.popleft()\n",
    "            if i == k and t == 1:\n",
    "                return ans\n",
    "            if t > 1:\n",
    "                q.append([t - 1, i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        while True:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] -= 1\n",
    "                    ans += 1\n",
    "                if tickets[k] == 0:\n",
    "                    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        count=0\n",
    "        for i in tickets:            \n",
    "            if i>tickets[k]:\n",
    "                count+=tickets[k]\n",
    "            else:\n",
    "                count+=i\n",
    "        for i in range(k+1,len(tickets)):\n",
    "            if tickets[i]>=tickets[k]:\n",
    "                count-=1    \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        length=len(tickets)\n",
    "        times=0\n",
    "        end=False\n",
    "        j=0\n",
    "        while not end:\n",
    "            if tickets[k]==0:\n",
    "                break\n",
    "            if tickets[j]>0:\n",
    "                times+=1\n",
    "            tickets[j]-=1\n",
    "            j+=1\n",
    "            if j==length:\n",
    "                j=0\n",
    "        return times\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        t = tickets[k]\n",
    "        return sum(min(n, t - (i > k)) for i, n in enumerate(tickets))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(tickets)):\n",
    "            if i <= k:\n",
    "                ans += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                ans += min(tickets[i], tickets[k]-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        \"\"\"思路: 模拟过程法\"\"\"\n",
    "        res = 0\n",
    "        while tickets[k] > 0:\n",
    "            for index in range(len(tickets)):\n",
    "                if tickets[index] > 0:\n",
    "                    tickets[index] -= 1\n",
    "                    res += 1\n",
    "                if tickets[k] == 0:\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans, idx = 0, 0\n",
    "        while tickets[k] > 0:\n",
    "            if tickets[idx] > 0:\n",
    "                tickets[idx] -= 1\n",
    "                ans += 1\n",
    "            idx = (idx + 1) % len(tickets)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        t = tickets[k]\n",
    "        return sum(min(n, t - 1 if i > k else t) for i, n in enumerate(tickets))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        i=0\n",
    "        time=0\n",
    "        if len(tickets)==0:\n",
    "            return tickets[0]\n",
    "        while tickets[k]!=0:\n",
    "            if tickets[i]>0:\n",
    "                tickets[i]-=1\n",
    "                time+=1\n",
    "            i+=1\n",
    "            if i==len(tickets):\n",
    "                i=0\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        while tickets[k] != 0:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] -= 1\n",
    "                    ans += 1\n",
    "                if tickets[k] == 0:\n",
    "                    return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        '''\n",
    "        1.对于在k前面的人，每轮都有优先权，如果所要票数小于tickets[k]，必然先买完自身所需tickets[i]，\n",
    "如果大于，那k买完就结束了，只能买到tickets[k]张，所以能买到min(tickets[i], tickets[k])张\n",
    "    2.对于在k后面的人，最多只能买到结束前一轮的，即最多只能买到tickets[k]-1张，而小于这个数便能\n",
    "买完，所以能买到min(tickets[i], tickets[k] - 1)张\n",
    "\n",
    "作者：思故我还在\n",
    "链接：https://leetcode.cn/problems/time-needed-to-buy-tickets/description/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        \n",
    "        :param tickets: \n",
    "        :param k: \n",
    "        :return: \n",
    "        '''\n",
    "        n=len(tickets)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if i<=k:\n",
    "                ans+=min(tickets[i],tickets[k])\n",
    "            else:\n",
    "                ans+=min(tickets[i],tickets[k]-1)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        count=0\n",
    "        tickets[k]=(tickets[k],\"target\")\n",
    "        while tickets:\n",
    "            person=tickets.pop(0)\n",
    "            count+=1\n",
    "            if type(person)==tuple:\n",
    "                if person[0]==1:\n",
    "                    return count\n",
    "                tickets.append((person[0]-1,person[1]))\n",
    "            else:\n",
    "                if person-1:\n",
    "                    tickets.append(person-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(tickets)):\n",
    "            if i <= k:\n",
    "                ans += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                ans += min(tickets[i], tickets[k] - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        n = len(tickets)\n",
    "        while tickets[k]:\n",
    "            if tickets[i%n]:\n",
    "                tickets[i%n] = tickets[i%n]-1\n",
    "                ans = ans + 1\n",
    "            i=i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        times=0\n",
    "        while tickets[k]:\n",
    "            if k==0 and tickets[0]==1:return times+1\n",
    "            times+=1\n",
    "            if tickets[0]!=1:tickets.append(tickets[0]-1)\n",
    "            tickets.pop(0)\n",
    "            k-=1\n",
    "            if k==-1:k=len(tickets)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        list1 = tickets[:k]\n",
    "        list2 = tickets[k:]\n",
    "        n = tickets[k]\n",
    "        sum1 ,sum2 =  0 , 0\n",
    "        for i in list1:\n",
    "            sum1 += min(i,n)\n",
    "        for i in list2:\n",
    "            sum2 += min(i,n-1)\n",
    "        return sum1+sum2+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        t = 0\n",
    "        l = []\n",
    "        while tickets[k] > 0:\n",
    "            for i, ele in enumerate(tickets):\n",
    "                if i == k and ele == 1:\n",
    "                    return t+1\n",
    "                else:\n",
    "                    l.append(max(0, ele-1))\n",
    "                    if ele > 0:\n",
    "                        t += 1\n",
    "            tickets = l\n",
    "            l = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        t_time = 0\n",
    "        while True:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[k] == 0:\n",
    "                    return t_time\n",
    "                if tickets[i] != 0:\n",
    "                    t_time += 1\n",
    "                    tickets[i] = tickets[i] - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        result=0 \n",
    "        while tickets[k]>1:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] >0:\n",
    "                    tickets[i]=tickets[i]-1\n",
    "                    result+=1\n",
    "           # print(tickets)\n",
    "        for i in range(k+1):\n",
    "            if tickets[i]>0:\n",
    "                result+=1\n",
    "        #a=[i>0 for i in tickets[k+1::]].count(True)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(tickets)):\n",
    "            # 遍历计算每个人所需时间\n",
    "            if i <= k:\n",
    "                res += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[i], tickets[k] - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        s = sum([n >= tickets[k] for n in tickets[k + 1:]])\n",
    "        while tickets[k] != 0:\n",
    "            m = 100\n",
    "            for n in tickets:\n",
    "                if 0 < n < m:\n",
    "                    m = n\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] -= m\n",
    "                    ans += m\n",
    "        return ans - s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(tickets)):\n",
    "            if i < k: \n",
    "                res += min(tickets[i], tickets[k])\n",
    "            elif i == k:\n",
    "                res += tickets[k]\n",
    "            else:\n",
    "                res += min(tickets[i], tickets[k]-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        cnt = tickets[k]\n",
    "        time = 0\n",
    "        while cnt:\n",
    "            while k >= 0:\n",
    "                current = tickets.pop(0)\n",
    "                current -= 1\n",
    "                time += 1\n",
    "                if current:\n",
    "                    tickets.append(current)\n",
    "                k -= 1\n",
    "            k = len(tickets) - 1\n",
    "            cnt -= 1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        sums = 0\n",
    "        for x in tickets[:k]:\n",
    "            sums += min(x, tickets[k])\n",
    "        for x in tickets[k + 1:]:\n",
    "            sums += min(x, tickets[k] - 1)\n",
    "        return sums + tickets[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        count = k\n",
    "        for _ in range(k):\n",
    "            c = tickets.pop(0)\n",
    "            if c > 1:\n",
    "                tickets.append(c-1)\n",
    "\n",
    "        while tickets[0] != 1:\n",
    "            n = len(tickets)\n",
    "            for _ in range(n):\n",
    "                count += 1\n",
    "                c = tickets.pop(0)\n",
    "                if c > 1:\n",
    "                    tickets.append(c-1)\n",
    "        return count + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans  = 0\n",
    "        \n",
    "\n",
    "        while tickets[k] != 0:\n",
    "            if tickets[k] == 1:\n",
    "                for i in range(k+1):\n",
    "                    if tickets[i] != 0:\n",
    "                        ans+=1\n",
    "                return ans\n",
    "            else:\n",
    "                cnt = 0\n",
    "                for i in range(len(tickets)):\n",
    "                    if tickets[i] != 0:\n",
    "                        cnt += 1\n",
    "                        tickets[i] -= 1\n",
    "                ans += cnt\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "    #     \"\"\"思路1: 模拟过程法, 时间复杂度O(n * tickets[k]), 空间复杂度O(1)\"\"\"\n",
    "    #     res = 0\n",
    "    #     while tickets[k] > 0:\n",
    "    #         for index in range(len(tickets)):\n",
    "    #             if tickets[index] > 0:\n",
    "    #                 tickets[index] -= 1\n",
    "    #                 res += 1\n",
    "    #             if tickets[k] == 0:\n",
    "    #                 break\n",
    "    #     return res\n",
    "\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        \"\"\"思路2: 数学, 时间复杂度O(n), 空间复杂度O(1)\"\"\"\n",
    "        res = 0\n",
    "        for index in range(len(tickets)):\n",
    "            if index <= k:\n",
    "                res += min(tickets[index], tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[index], tickets[k] - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = tickets[k]\n",
    "        for i in range(k):\n",
    "            res += min(tickets[i],tickets[k])\n",
    "        for j in range(k+1,len(tickets)):\n",
    "            res += max(0,min(tickets[k]-1,tickets[j]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            # 遍历计算每个人所需时间\n",
    "            if i <= k:\n",
    "                res += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[i], tickets[k] - 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            # 遍历计算每个人所需时间\n",
    "            if i <= k:\n",
    "                res += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[i], tickets[k] - 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        t = 0\n",
    "        for n in tickets[:k+1]:\n",
    "            t += min(n, tickets[k])\n",
    "        for n in tickets[k+1:]:\n",
    "            t += min(n, tickets[k]-1)\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans  = 0 \n",
    "        for i in range(len(tickets)):\n",
    "            if i <= k  :\n",
    "                ans += min(tickets[i] ,tickets[k])\n",
    "            elif i > k  :\n",
    "                ans += min(tickets[k] -1 , tickets[i])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        n = len(tickets)\n",
    "        for i in range(n):\n",
    "             q.append([tickets[i],i])\n",
    "        while q:\n",
    "            cur,id = q.popleft()\n",
    "            ans += 1\n",
    "            cur -= 1\n",
    "            if cur == 0:\n",
    "                if id == k:\n",
    "                    return ans\n",
    "            else:\n",
    "                q.append([cur,id])\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if i<=k:\n",
    "                res+=min(tickets[i],tickets[k])\n",
    "            else:\n",
    "                res+=min(tickets[i],tickets[k]-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        return sum(min(tickets[k],x) if i<=k else min(tickets[k]-1,x) for i,x in enumerate(tickets))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        times = 0\n",
    "        for i in range(0, len(tickets)):\n",
    "            if i <= k:\n",
    "                times += tickets[k] if tickets[i] > tickets[k] else tickets[i]\n",
    "            else:\n",
    "                times += tickets[k] - 1 if tickets[i] >= tickets[k] else tickets[i]    \n",
    "\n",
    "        return times        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        # 有人i排在k前面，或者就是k（i<=k），在k买完之前，i可以买 ticket[i] 张，看谁先买完\n",
    "        # 有人i排在k后面（i>k），那么有可能k先比i买完，这种情况i可以买 ticket[k]-1 张，看谁先买完\n",
    "        # 因为要算在k的人买完票ticket[k]要多少时间\n",
    "        length = len(tickets)\n",
    "        res = 0\n",
    "        for i in range(length):\n",
    "            if i <= k:\n",
    "                # 排前面的，如果先买完，就归0，k位置还得继续排\n",
    "                res += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[k]-1, tickets[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        return sum(min(n, tickets[k] - (i > k)) for i, n in enumerate(tickets))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        res =0\n",
    "        for i in range(n):\n",
    "            if i<=k:\n",
    "                res+=min(tickets[i],tickets[k])\n",
    "            else:\n",
    "                res+=min(tickets[i],tickets[k]-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        # filtered_list = [elem for elem in original_list if elem != 0]\n",
    "        # modified_array = [elem - 1 for elem in original_array]\n",
    "\n",
    "        time = 0\n",
    "        aim_number = tickets[k]\n",
    "        f = 0\n",
    "\n",
    "        if k<len(tickets)-1:\n",
    "            filtered_list = tickets[k+1:]\n",
    "            f_list = [elem for elem in filtered_list if elem>=aim_number]\n",
    "            f = len(f_list)\n",
    "\n",
    "        for i in range(aim_number):\n",
    "            time = len(tickets) + time\n",
    "            tickets_1 = [elem - 1 for elem in tickets]\n",
    "            tickets = [elem for elem in tickets_1 if elem != 0]\n",
    "        return time-f\n",
    "\n",
    "'''\n",
    "[84,49,5,24,70,77,87,8]\n",
    "[79,44,19,65,72,82,3]   5\n",
    "[76,41,16,62,69,79]     3\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        t = 0\n",
    "        l = []\n",
    "        while True:\n",
    "            for i, ele in enumerate(tickets):\n",
    "                if i == k and ele == 1:\n",
    "                    return t+1\n",
    "                else:\n",
    "                    l.append(max(0, ele-1))\n",
    "                    if ele > 0:\n",
    "                        t += 1\n",
    "            tickets = l\n",
    "            l = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = tickets[k]\n",
    "        for i, num in enumerate(tickets):\n",
    "            if i < k:\n",
    "                if num > tickets[k]:\n",
    "                    res += tickets[k]\n",
    "                else:\n",
    "                    res += num\n",
    "            elif i > k:\n",
    "                if num >= tickets[k]:\n",
    "                    res += tickets[k] - 1\n",
    "                else:\n",
    "                    res += num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(tickets)):\n",
    "            if i <= k:\n",
    "                res += min(tickets[i],tickets[k])\n",
    "            elif i > k:\n",
    "                res += min(tickets[i],tickets[k]-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        res = 0\n",
    "        for i in range (n):\n",
    "            if i<=k:\n",
    "                res += min(tickets[i],tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[k]-1,tickets[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n=len(tickets)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if i<k:\n",
    "                ans+=min(tickets[i],tickets[k])\n",
    "            elif i>k:\n",
    "                ans+=min(tickets[i],tickets[k]-1)\n",
    "\n",
    "        return ans+tickets[k]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        return sum(min(t, tickets[k]) if i <= k else min(t, tickets[k]-1)  for i,t in enumerate(tickets))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        tickets = deque(tickets)\n",
    "        n = len(tickets)\n",
    "        while tickets[k] != 0:\n",
    "            cur = tickets.popleft()\n",
    "            if cur != 0:\n",
    "                cur -= 1\n",
    "                ans += 1\n",
    "            tickets.append(cur)\n",
    "            k -= 1\n",
    "            k = k + n if k < 0 else k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "\n",
    "        return sum(min(ticket, tickets[k] if idx <= k else tickets[k] -1) for idx, ticket in enumerate(tickets))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        p=0\n",
    "        ans=0\n",
    "        while 1:\n",
    "            tickets[p]-=1\n",
    "            ans+=1\n",
    "            if tickets[k]==0:\n",
    "                return ans\n",
    "            p=(p+1)%len(tickets)\n",
    "            while tickets[p]==0:\n",
    "                p = (p + 1) % len(tickets)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\r\n",
    "        member_counts = collections.defaultdict(int)\r\n",
    "        \r\n",
    "\r\n",
    "        if tickets[k] == 1:\r\n",
    "            return k + 1\r\n",
    "        \r\n",
    "        for i in range(len(tickets)):\r\n",
    "            member_counts[tickets[i]] += 1\r\n",
    "\r\n",
    "        time = 0\r\n",
    "        for least in range(1,tickets[k]):\r\n",
    "            for key,value in member_counts.items():\r\n",
    "                if key >= least:\r\n",
    "                    time += value\r\n",
    "        \r\n",
    "        for j in range(0,k+1):\r\n",
    "            if tickets[j] >= tickets[k]:\r\n",
    "                time += 1\r\n",
    "\r\n",
    "        \r\n",
    "        return time \r\n",
    "            \r\n",
    "        \r\n",
    "        \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(tickets)):\n",
    "            if tickets[i] >= tickets[k]:\n",
    "                ans += tickets[k] - (i > k)\n",
    "            else:\n",
    "                ans += tickets[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        times=0\n",
    "        while tickets[k]!=0:\n",
    "            if k==0 and tickets[0]==1:return times+1\n",
    "            times+=1\n",
    "            if tickets[0]!=1:tickets.append(tickets[0]-1)\n",
    "            tickets.pop(0)\n",
    "            k-=1\n",
    "            if k==-1:k=len(tickets)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        k_tickets=tickets[k]\n",
    "        sum_tickets=0\n",
    "        for i in tickets:\n",
    "            sum_tickets+=i\n",
    "        queue=[]\n",
    "        i=0\n",
    "        while i<sum_tickets:\n",
    "            for j in range(len(tickets)):\n",
    "                if tickets[j]!=0:\n",
    "                    tickets[j]-=1\n",
    "                    queue.insert(0,j)\n",
    "                    i+=1\n",
    "        t=0\n",
    "        while k_tickets>0:\n",
    "            if queue[-1]==k:\n",
    "                k_tickets-=1\n",
    "            t+=1\n",
    "            queue.pop()\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\r\n",
    "        #member_counts = collections.defaultdict(int)\r\n",
    "        member_counts = [0] * 100\r\n",
    "\r\n",
    "        if tickets[k] == 1:\r\n",
    "            return k + 1\r\n",
    "        \r\n",
    "        for i in range(len(tickets)):\r\n",
    "            member_counts[tickets[i]-1] += 1\r\n",
    "\r\n",
    "        time = 0\r\n",
    "        for least in range(1,tickets[k]):\r\n",
    "            # for key,value in member_counts.items():\r\n",
    "                # if key >= least:\r\n",
    "                #     time += value\r\n",
    "            time += sum(member_counts[least-1:])\r\n",
    "        \r\n",
    "        for j in range(0,k+1):\r\n",
    "            if tickets[j] >= tickets[k]:\r\n",
    "                time += 1\r\n",
    "\r\n",
    "        \r\n",
    "        return time \r\n",
    "            \r\n",
    "        \r\n",
    "        \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\r\n",
    "        #暴力哈希\r\n",
    "        #member_counts = collections.defaultdict(int)\r\n",
    "        member_counts = [0] * 100\r\n",
    "\r\n",
    "        # if tickets[k] == 1:#特殊情况\r\n",
    "        #     return k + 1\r\n",
    "        \r\n",
    "        for i in range(len(tickets)):\r\n",
    "            member_counts[tickets[i]-1] += 1\r\n",
    "\r\n",
    "        time = 0\r\n",
    "        for least in range(1,tickets[k]):\r\n",
    "            # for key,value in member_counts.items():\r\n",
    "                # if key >= least:\r\n",
    "                #     time += value\r\n",
    "            time += sum(member_counts[least-1:])\r\n",
    "        \r\n",
    "        for j in range(0,k+1):\r\n",
    "            if tickets[j] >= tickets[k]:\r\n",
    "                time += 1\r\n",
    "\r\n",
    "        \r\n",
    "        return time \r\n",
    "            \r\n",
    "        \r\n",
    "        \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        if tickets[k] == 1:\n",
    "            return k+1\n",
    "        elif len(tickets) == 1:\n",
    "            return tickets[k]\n",
    "\n",
    "        totalTime = 0\n",
    "        for i in range(k + 1):\n",
    "            totalTime += 1\n",
    "            tickets[i] -= 1\n",
    "\n",
    "        tickets.append(tickets.pop(k))\n",
    "        while tickets[-1] > 0:\n",
    "            while 0 in tickets:\n",
    "                tickets.remove(0)\n",
    "\n",
    "            for i in range(len(tickets)):\n",
    "                totalTime += 1\n",
    "                tickets[i] -= 1\n",
    "        return totalTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(tickets)):\n",
    "            # 遍历计算每个人所需时间\n",
    "            if i <= k:\n",
    "                res += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[i], tickets[k] - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        time = 0\n",
    "        while tickets[k] != 0:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[i] != 0:\n",
    "                    time += 1\n",
    "                    tickets[i] -= 1\n",
    "                if tickets[k] == 0:\n",
    "                    return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        if tickets[k] == 1:\n",
    "            return k + 1\n",
    "        cost = 0 \n",
    "        while tickets[k] > 0:\n",
    "            for i in range(len(tickets)):\n",
    "                if tickets[k] == 0:\n",
    "                    return cost\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] = tickets[i] - 1\n",
    "                    cost += 1\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            # 遍历计算每个人所需时间\n",
    "            if i <= k:\n",
    "                res += min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                res += min(tickets[i], tickets[k] - 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i, v in enumerate(tickets):\n",
    "            c = tickets[k] if i <= k else tickets[k]-1\n",
    "            ans += min(v, c)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        # for i in range(len(tickets)):\n",
    "        #     if tickets[i] != 0:\n",
    "        #         tickets[i] -= 1\n",
    "        #         res += 1\n",
    "        i, ans = 0, 0\n",
    "        while tickets[k] != 0:\n",
    "            if tickets[i % len(tickets)] != 0:\n",
    "                tickets[i % len(tickets)] -= 1\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res = tickets[k]\n",
    "        for i in range(k):\n",
    "            res += min(tickets[i],tickets[k])\n",
    "        for j in range(k+1,len(tickets)):\n",
    "            res += min(tickets[k]-1,tickets[j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        for i in range(len(tickets)):\n",
    "            if i<=k:\n",
    "                res+=min(tickets[i], tickets[k])\n",
    "            else:\n",
    "                res+=min(tickets[i], tickets[k]-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        n = len(tickets)\n",
    "        t = 0 \n",
    "        while True:\n",
    "            for i in range(n):\n",
    "                if tickets[i] > 0:\n",
    "                    tickets[i] -= 1\n",
    "                    t += 1\n",
    "                if tickets[k] == 0:\n",
    "                    return t \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        mx = tickets[k]\n",
    "        res = 0;f = 1\n",
    "        for idx,i in enumerate(tickets):\n",
    "            if idx > k and f:mx -= 1;f = 0\n",
    "            res += i if i <= mx else mx\n",
    "            print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:\n",
    "        return sum(min(tickets[k], num) for num in tickets) - sum(int(num >= tickets[k]) for num in tickets[k+1:])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
